1685. Lands of Antarctica

Dots on the map of Antarctica shows the n polar stations, each of which has natural coordinates in a rectangular grid. The transition between the two stations is possible if the distance between them in a straight line less than two unit segments of the map. Stations, between which there exists a direct or indirect paths, are united into the land. Each station belongs to one land only.

You must find the number k of Arctic lands.

Input. The first line contains the number n of stations. Each of the next n lines contains two numbers – the coordinates of each station. All values are positive integers and do not exceed 100.

Output. Print the number of lands.

Sample input	Sample output
10 2 4 6 2 2 1 2 6 4 3 4 1 1 5 5 2 1 3 3 5	3

SOLUTION

graphs – depth first search

Algorithm analysis

In a two-dimensional array m, create a map of Antarctica: m[i][j] = 1 if the polar station is in position (i, j) and m[i][j] = 0 otherwise.

On the resulting grid, find the number of connective components. From the cell you can move in eight directions (vertically, horizontally and diagonally).

Example

The next figure shows the map of Antarctica for the given sample. This map contains three connected components.

Algorithm realization

Declare a two-dimensional array m, where we store the map of Antarctica.

#define MAX 101

int m[MAX][MAX];

The function dfs performs a depth first search in a rectangular grid, starting from the point (i, j). Make moves in all eight directions.

void dfs(int i, int j)

{

if ((i < 0) || (j < 0) || (i >= MAX) || (j >= MAX)) return;

if (m[i][j] == 0) return;

m[i][j] = 0;

dfs(i + 1, j - 1); dfs(i + 1, j); dfs(i + 1, j + 1);

dfs(i, j - 1); dfs(i, j + 1);

dfs(i - 1, j - 1); dfs(i - 1, j); dfs(i - 1, j + 1);

}

The main part of the program. Read the input data. Build a labyrinth – a map of Antarctica.

scanf("%d", &n);

for (i = 0; i < n; i++)

{

scanf("%d %d", &a, &b);

m[a][b] = 1;

}

In the variable c count the number of Arctic lands.

c = 0;

Run the depth first search on the grid. Iterate over the cells of two-dimensional array and for each cell with the Arctic station (for which m[i][j] = 1) start the depth first search dfs(i, j). With each call of the dfs function, the number of lands is increased by 1.

for (i = 0; i < MAX; i++)

for (j = 0; j < MAX; j++)

if (m[i][j] == 1)

{

dfs(i, j);

c++;

}

Print the answer.

printf("%d\n", c);